﻿// 0808train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <limits>

using namespace std;

/*
 上面的人要比下面的人矮一点, 轻一点
 已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人
 输入：height = [65,70,56,75,60,68]  weight = [100,150,90,190,95,110]
 输出：6
 解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)
 */

int solve01(vector<int>&height, vector<int>&weight)
{
    int vec_size = height.size();
    vector<pair<int, int>>pair_vec(vec_size);

    for (int i=0; i<vec_size; i++)
    {
        pair_vec[i] = make_pair(height[i], weight[i]);
    }

    sort(pair_vec.begin(), pair_vec.end(), [](pair<int, int>& a, pair<int, int>& b)
        {
            if (a.first==b.first)
            {
                return a.second < b.second;
            }
            return a.first < b.first;
        });

    vector<int>dynamic_vec(vec_size, 1);

    for (int curr=1; curr<vec_size; curr++)
    {
        for (int prev=0; prev<curr; prev++)
        {
            pair<int,int> curr_pair = pair_vec[curr];
            pair<int, int> prev_pair = pair_vec[prev];
	        if (prev_pair.first<curr_pair.first && prev_pair.second< curr_pair.second)
	        {
                dynamic_vec[curr] = dynamic_vec[prev] + 1;
	        }
        }

    }

    int max_count = 1;
    for (auto&curr_count:dynamic_vec)
    {
        max_count = max(max_count, curr_count);
    }
    return max_count;

    //solve01
}


/*
 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
-  nums1[i] == nums2[j]
- 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。

输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2

 */
int solve02(vector<int>&nums1, vector<int>&nums2)
{
    vector<int>col_vec = nums1;
    vector<int>row_vec = nums2;

    int col_size = col_vec.size() + 1;
    int row_size = row_vec.size() + 1;

    vector<vector<int>>dynamic_vec(row_size, vector<int>(col_size, 0));

    //col==0, 说明col_vec为空，第一列全为0
    //row==0, 说明row_vec为空，第一行全为0
    //所以这里从1行1列开始
    int max_length = 0;
    for (int row=1; row<row_size; row++)
    {
        for (int col=1; col<col_size; col++)
        {
            if (col_vec[col-1]==row_vec[row-1])
            {
                dynamic_vec[row][col] = dynamic_vec[row - 1][col - 1] + 1;
            }
            else
            {
                int max_only_one = max(dynamic_vec[row - 1][col], dynamic_vec[row][col - 1]);
                dynamic_vec[row][col] = max_only_one;
            }
            max_length = max(max_length, dynamic_vec[row][col]);
        }
    }


    return max_length;

    //solve02------
}


/*
输入
输入的参数text1，text2分别表示两行代码

输出
输出任一最长公共子串。

输入
hello123world
hello123abc4
输出
hello123

 */

void solve03(string&text1, string&text2)
{
    string col_str = text1;
    string row_str = text2;

    int col_size = col_str.size() + 1;
    int row_size = row_str.size() + 1;

    vector<vector<int>>dynamic_vec(row_size, vector<int>(col_size, 0));

    int max_length = 0;
    int max_col_index = -1;
    //第0列表示col_str为空，全为0
    //第0行表示row_str为空，全为0
    for (int row=1; row<row_size; row++)
    {
        for (int col=1; col<col_size; col++)
        {
            if (row_str[row-1]==col_str[col-1])
            {
                dynamic_vec[row][col] = dynamic_vec[row - 1][col - 1] + 1;
            }
            if (dynamic_vec[row][col] > max_length)
            {
                max_length = dynamic_vec[row][col];
                max_col_index = col;
            }
        }
    }

    if (max_length==0)
    {
        cout << "";
        return;
    }
    int start_index = max_col_index - max_length;
    string result = col_str.substr(start_index, max_length);
    cout << result;

    //solve03------
}

int main()
{
	{
        //string text1 = "hello123world";
        //string text2 = "hello123abc4";
        string text1;
        cin >> text1;
        string text2;
        cin >> text2;

        solve03(text1, text2);

        return 0;
	}

	{
        //nums1 = [1,4,2], nums2 = [1,2,4]
        vector<int>nums1 = { 1,4,2 };
        vector<int>nums2 = { 1,2,4 };

        cout << solve02(nums1, nums2);

        return 0;
	}

    //height = [65,70,56,75,60,68]  weight = [100,150,90,190,95,110]
    vector<int>height = { 65,70,56,75,60,68 };
    vector<int>weight = { 100,150,90,190,95,110 };
    cout << solve01(height, weight);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
